package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;



/**
 * Description 计数排序 待排数组只能为正整数
 *
 * @ClassName algorithm.sort.CountingSort
 * @Version 1.0
 * @Date: 2022/2/18 17:22
 * @Author xuyi
 */
public class CountingSort {
    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public void sort(int[] arr){
        if(arr == null||arr.length<2){
            return;
        }
        countingSort(arr);
    }

    private void countingSort(int[] arr){
        int bucketLength = getMax(arr)+1;
        int[] bucket  = new int[bucketLength];
        for(int num:arr){
            bucket[num]++;
        }

        int idx = 0;
        for(int i=0;i<bucket .length;i++){
            while(bucket [i]>0){
                arr[idx++]=i;
                bucket [i]--;
            }
        }
    }

    private int getMax(int[] arr){
        int max = arr[0];
        for(int i =1;i<arr.length;i++){
            if(arr[i]>max){
                max = arr[i];
            }
        }
        return max;
    }
}
